package 二叉树;

import java.util.Deque;
import java.util.LinkedList;

//513 找树左下角的值
public class Solution10 {
    //BFS
    public int findBottomLeftValue1(TreeNode root) {
        int ans = -1;
        Deque<TreeNode> queue = new LinkedList();
        queue.addLast(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i =0;i<size;i++){
                TreeNode node = queue.pollFirst();
                if(i==0)ans = node.val;
                if(node.left!=null) queue.addLast(node.left);
                if(node.right!=null) queue.addLast(node.right);
            }
        }
        return ans;
    }
    //DFS
    public int findBottomLeftValue2(TreeNode root) {
        dfs(root,1);
        return ans;
    }
    int maxDepth =0;
    int ans = -1;
    void dfs(TreeNode root, int depth){
        if(root==null)return;
        if(depth>maxDepth){
            ans=root.val;
            maxDepth=depth;
        }
        dfs(root.left,depth+1);
        dfs(root.right,depth+1);
    }
}
